home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / clean / sun3.lha / Sun3 / seqdemos / invperm.icl < prev    next >
Text File  |  1992-08-07  |  2KB  |  72 lines
  1. MODULE invperm;
  2.  
  3. <<
  4. Inverse Permutation.
  5.  
  6. Inverts the permutation represented by the list InitPerm.
  7. When a permutation of the form (n,n-1,...,2,1) is inverted this
  8. algorithm runs in linear time. The average (and worst) case
  9. behavior is however quadratic (in the size of the permutation).
  10. >>
  11.  
  12. IMPORT deltaI, deltaM;
  13.  
  14. TYPE
  15.  
  16. <<  A permutation (Perm) is represented as a list of integers.
  17.     The resulting inverse permutation (TPerm) is built up as a list of
  18.     tuples (TElt) containing an elements and its index, sorted on index.
  19. >>
  20. ::  Perm    -> [INT];
  21. ::  Index   -> INT;
  22. ::  TElt    -> (Index,INT);
  23. ::  TPerm   -> [TElt];
  24.  
  25.  
  26. RULE
  27.  
  28. <<  The initial permutation.
  29.     inverse: [10,12,17,7,1,11,19,18,3,8,4,6,5,14,15,16,2,9,13].
  30. >>
  31. ::  InitPerm -> Perm;
  32.     InitPerm -> [5,17,9,11,13,12,4,10,18,1,6,2,19,14,15,16,3,8,7];
  33.  
  34.  
  35. ==  InvPerm returns the inverse of the permutation p by means of calling Ip.
  36.  
  37. ::  InvPerm Perm -> Perm;
  38.     InvPerm p -> Ip 1 [] p;
  39.  
  40.  
  41. <<  Ip inverts a permutation (3rd arg) by using the i'th element of
  42.     the initial permutation as index for i, which becomes the element
  43.     of the inverse permutation ('imperative': ip[p[i]] := i). At the
  44.     end the indices have to be removed from the inverse by means of 
  45.     the function Strip.
  46. >>
  47. ::  Ip Index TPerm Perm -> Perm;
  48.     Ip i ip []      -> Strip ip;
  49.     Ip i ip [e|pr]  -> Ip (++ i) (Update ip e i) pr;
  50.  
  51.  
  52. <<  Update adds an element to a list of (index,value)-pairs (a TPerm)
  53.     that is sorted on index.
  54. >>
  55. ::  Update TPerm Index INT      -> TPerm;
  56.     Update []             i x   -> [(i,x)];
  57.     Update [e:(j,y) | ar] i x   -> [(i,x), e | ar]    , IF < i j
  58.                                 -> [e | Update ar i x];
  59.  
  60.  
  61. ==  Strip removes the (superfluous) indices from the resulting permutation.
  62.  
  63. ::  Strip TPerm -> Perm;
  64.     Strip [] -> [];
  65.     Strip [(i,x)|ar] -> [x | Strip ar];
  66.  
  67.  
  68. ==  The Start rule: invert the initial permutation.
  69.  
  70. ::  Start -> Perm;
  71.     Start -> InvPerm InitPerm;
  72.